package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/rotate-list/
 * 61. 旋转链表
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 * 示例：
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 */
public class LeetCode61 {
    static class Solution {
        /**
         * 时间复杂度：O(n)
         * 空间复杂度：O(1)
         */
        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || head.next == null) return head;
            int len = 0;
            ListNode n = head;
            // 计算链表长度
            while (n.next != null) {
                len++;
                n = n.next;
            }
            len++;
            k = k % len; // 有效旋转次数
            if (k <= 0) return head;
            // 闭环
            n.next = head;

            // 确定首尾
            ListNode newTail = head;
            for (int i = 0; i < len - k - 1; i++) {
                newTail = newTail.next;
            }
            ListNode newHead = newTail.next;
            newTail.next = null;
            return newHead;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution solution = new Solution();
        ListNode res = solution.rotateRight(head, 2);
        show(res);
    }
    static void show(ListNode head) {
        while (head != null) {
            System.out.print(head.val + ", ");
            head = head.next;
        }
    }
}
